package com.zq.solution.listnode;

/**
 * @ClassName AddTwoNumbers
 * @Description 两数相加
 * 给出两个非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * 您可以假设除了数字 0 之外，这两个数都不会以 0开头。
 * 示例：
 *   输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 *   输出：7 -> 0 -> 8
 *   原因：342 + 465 = 807
 * @Author ZQ
 * @Date 2020/10/21 21:33
 * @Version 1.0
 */
public class AddTwoNumbers {
    public ListNode<Integer> addTwoNumbers(ListNode<Integer> l1, ListNode<Integer> l2) {
        return addTwoNumbers2(addTwoNumbers1(l1,l2));
    }
    public ListNode<Integer> addTwoNumbers1(ListNode<Integer> l1, ListNode<Integer> l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode<Integer> node = new ListNode<>();
        node.val = l1.val + l2.val;
        node.next = addTwoNumbers1(l1.next,l2.next);
        return node;
    }
    public ListNode<Integer> addTwoNumbers2(ListNode<Integer> node) {
        if (node == null) return null;
        if (node.val >= 10){
            node.val = node.val % 10;
            if (node.next == null){
                node.next = new ListNode<>(1);
            }else{
                node.next.val += 1;
            }
        }
        node.next = addTwoNumbers2(node.next);
        return node;
    }
}
